BZOJ4001【TJOI2015】概率论 <生成函数>

Problem

【TJOI2015】概率论

Description

Input

输入一个正整数，代表有根树的节点数。

Output

输出这棵树期望的叶子节点数。要求误差小于。

Sample Input

1

Sample Output

1.000000000

Hint

标签：生成函数

Solution

生成函数结论题。

1. 构造递推式

考虑用表示个结点的树的所有形态中叶子结点的个数和，用表示个结点的树的所有形态数。则叶子个数的期望为。

首先计算。对于个结点的二叉树，去掉根后还剩个结点，若左子树中有个结点，则右子树中有个结点，可知左子树有种形态，右子树有种形态，因此此种情况下树的形态数为。故有。
然后计算。对于个结点的二叉树，若左子树中有个结点，右子树中有个结点，可知叶子结点个数和会增加。于是有。

2. 构造生成函数

补充定义构造的生成函数：

对于，有，于是。同理，对于，将展开后与比较，可得。

由此，解二次方程

可得

（已根据带入后得出结果的正负性舍去每个函数的另一种取值。）

3. 解递推式通项

接下来用广义二项式定理展开并求出的通项。

定义广义下的二项式系数为

有定理

则有特殊形式

因此

分别化简两个函数中带广义二项式系数的系数

分别带回原生成函数得

因此有通项

综上，可得答案。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    double n; scanf("%lf", &n);
    printf("%.9lf\n", n*(n+1)/(4*n-2));
    return 0;
}